#include<stdlib.h>

int* Next(char* dest) {
    int len = 0;
    while (dest[len] != '\0') {
        len++;
    }
    int* next = (int*)malloc((len + 1) * sizeof(int));
    next[0] = 0;
    for (int i = 1, j = 0; i < len; i++) {
        while (j > 0 && dest[i] != dest[j]) {
            j = next[j - 1];
        }
        if (dest[i] == dest[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

int strStr(char* haystack, char* needle) {
    int len1 = 0;
    while (haystack[len1] != '\0') {
        len1++;
    }
    int len2 = 0;
    while (needle[len2] != '\0') {
        len2++;
    }
    int* next = Next(needle);
    for (int i = 0, j = 0; i < len1; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == len2) {
            free(next);
            return i - j + 1;
        }
    }
    free(next);
    return -1;
}